#pragma once
#include <algorithm>

namespace qb{
	namespace base{

#ifndef BASSERT
#define BASSERT //
#endif // !BASSERT

#ifdef QBFLAG_DOUBLELINKLIST_ASSERT_VALID
#define CHECK_LIST(LIST)  (LIST)->Check()
#define DEBUG_ASSERT(S)	BASSERT(S)
#define DEBUG_ASSERT_FALSE(S)	BASSERT_FALSE(S)
#else
#define CHECK_LIST(LIST)
#define DEBUG_ASSERT(S)
#define DEBUG_ASSERT_FALSE(S)
#endif
#define CHECK_SINGLE(PTR) DEBUG_ASSERT(PTR && PTR->GetNext() == nullptr && PTR->GetPrev() == nullptr);


		template<class T>
		class DoubleLinkList{
		private:
			class TType{
			public:
				TType* GetNext()const{ return nullptr; }
				TType* GetPrev()const{ return nullptr; }
				void SetNext(TType*){}
				void SetPrev(TType*){}
			};

		protected:
			typedef T* Pointer;
			typedef DoubleLinkList<T> ThisType;
			Pointer		m_head;
			Pointer		m_tail;
			int			m_count;
		private:
			DoubleLinkList(const DoubleLinkList&) = delete;
			DoubleLinkList& operator=(const DoubleLinkList&) = delete;
		public://双链表静态工具函数


			static void Join(T* prev, T* next)
			{
				// 将两个双链表连接起来,prev是前一个的末尾,next是后一个的开头
				DEBUG_ASSERT(prev && prev->GetNext() == nullptr);
				DEBUG_ASSERT(next && next->GetPrev() == nullptr);
				prev->SetNext(next);
				next->SetPrev(prev);
			}
			static void Cut(T* t)
			{
				// 将t所在的双链表从t前面剪断
				T* prev = t->GetPrev();
				if (prev)prev->SetNext(nullptr);
				t->SetPrev(nullptr);
			}
			static void Unlink(T* t)
			{
				// 将t从其所在的双链表中取出来
				T* prev = t->GetPrev();
				T* next = t->GetNext();
				if (prev)prev->SetNext(next);
				if (next)next->SetPrev(prev);
				t->SetNext(nullptr);
				t->SetPrev(nullptr);
			}
			static void Link(T* prev, T* t, T* next)
			{
				// 将t放在双链表中,其前面是prev,后面是next,prev和next必须满足前后关系
				CHECK_SINGLE(t);
				DEBUG_ASSERT((prev != next) && (!prev || prev->GetNext() == next) && (!next || next->GetPrev() == prev));
				t->SetPrev(prev); t->SetNext(next);
				if (prev)prev->SetNext(t);
				if (next)next->SetPrev(t);
			}
			static T*   GetPrev(T* t, unsigned int offset)
			{
				// 获取双链表中t之后的一定偏移位置的表项,0即其本身t
				// offset不能超过t之后的长度
				T* cur = t; int pos = offset;
				while (cur && pos > 0){ cur = cur->GetPrev(); --pos; }
				DEBUG_ASSERT(pos == 0 && cur!=nullptr);
				return cur;
			}
			static T*   GetNext(T* t, unsigned int offset)
			{
				// 获取双链表中t之后的一定偏移位置的表项,0即其本身t
				// offset不能超过t之后的长度
				T* cur = t; int pos = offset;
				while (cur && pos > 0){ cur = cur->GetNext(); --pos; }
				DEBUG_ASSERT(pos == 0 && cur!=nullptr);
				return cur;
			}
			static int  Find(const T* begin, int ncount, const T* t)
			{
				// 在双链表begin,end中找出t,通常
				if (begin == nullptr || t == nullptr || ncount <= 0)
					return -1;
				const T* cur = begin;
				for (int i = 0; cur && i < ncount; i++, cur = cur->GetNext())
					if (cur == t)
						return i;
				return -1;
			}
		public:
			DoubleLinkList() :m_head(nullptr), m_tail(nullptr), m_count(0){}
			inline void Reset(){ m_head = nullptr; m_tail = nullptr; m_count = 0; }
			void Swap(DoubleLinkList& list){
				std::swap(m_head, list.m_head);
				std::swap(m_tail, list.m_tail);
				std::swap(m_count, list.m_count);
			}
			inline Pointer GetHead()const{ return m_head; }
			inline Pointer GetTail()const{ return m_tail; }
			inline int GetCount()const{ return m_count; }
			void AddCount(){ m_count++; }
			void InsertAfter(Pointer ptrExist, Pointer ptrNew)
			{
				DEBUG_ASSERT(ptrExist);
				CHECK_SINGLE(ptrNew);
				Link(ptrExist, ptrNew, ptrExist->GetNext());
				if (ptrExist == m_tail)
					m_tail = ptrNew;
				m_count++;
				CHECK_LIST(this);
			}
			void InsertBySpace(Pointer page, int maxStep)
			{
				DEBUG_ASSERT(Check());
				if (m_head == nullptr || page->GetSpace() >= m_head->GetSpace())
					InsertHead(page);
				else
				{
					BASSERT(m_tail && m_head);
					m_head->LinkBySpace(page, maxStep);
					while (m_tail->GetNext())
					{
						m_tail = m_tail->GetNext();
					}
					m_count++;
					BASSERT(page->GetNext() != nullptr || page->GetPrev() != nullptr);
				}
				DEBUG_ASSERT(Check());
			}

			void InsertHead(Pointer page)
			{
				DEBUG_ASSERT(page && page->GetNext() == nullptr && page->GetPrev() == nullptr);
				CHECK_LIST(this);
				if (m_count > 0)
				{
					page->SetNext(m_head);
					m_head->SetPrev(page);
					m_head = page;
				}
				else
					m_head = m_tail = page;
				m_count++;
				CHECK_LIST(this);
			}
			void Append(Pointer ptr)
			{
				CHECK_SINGLE(ptr);
				if (m_count <= 0){ m_head = m_tail = ptr; m_count = 1; }
				else{
					m_tail->SetNext(ptr); ptr->SetPrev(m_tail);
					m_tail = ptr; m_count++;
				}
			}
			Pointer PickTail()
			{
				/*if (page == m_slots[m_lastslot].head)
				m_slots[m_lastslot].head = page->GetNext();
				page->Unlink();*/
				DEBUG_ASSERT(Check());
				Pointer page = nullptr;
				CHECK_LIST(this);
				if (m_count > 0)
				{
					page = m_tail;
					m_tail = m_tail->GetPrev();
					DoubleLinkList<T>::Unlink(page);
					m_count--;
					if (page == m_head)
					{
						m_head = nullptr;
						m_tail = nullptr;
						m_count = 0;
					}
				}
				CHECK_LIST(this);
				DEBUG_ASSERT(Check());
				return page;
			}
			Pointer PickHead()
			{
				Pointer page = nullptr;
				CHECK_LIST(this);
				if (m_count > 0)
				{
					page = m_head;
					m_head = m_head->GetNext();
					DoubleLinkList<T>::Unlink(page);
					m_count--;
					if (page == m_tail)
					{
						m_head = nullptr;
						m_tail = nullptr;
						m_count = 0;
					}
				}
				CHECK_LIST(this);
				return page;
			}
			void Pick(int pos, int ncount, ThisType& queue)
			{
				// 将从pos开始ncount个的双链表项提取到新的空的双链表队列queue中
				DEBUG_ASSERT(queue.GetCount() <= 0);
				if (m_count <= 0 || pos >= m_count || pos < 0 || ncount <= 0)
					return;
				if (pos + ncount >= m_count)
					ncount = m_count - pos;
				queue.Reset();
				Pointer head = m_head;
				Pointer tail = m_tail;
				Pointer start = DoubleLinkList<T>::GetNext(m_head, pos); DEBUG_ASSERT(start);
				Pointer end = DoubleLinkList<T>::GetNext(start, ncount - 1); DEBUG_ASSERT(end);
				Pointer start_prev = start ? start->GetPrev() : nullptr;
				Pointer next_head = end == tail ? nullptr : end->GetNext();
				m_head = (head != start) ? head : next_head;
				m_tail = next_head ? m_tail : start_prev;
				m_count -= ncount;
				DoubleLinkList<T>::Cut(start);
				if (next_head)
					DoubleLinkList<T>::Cut(next_head);
				if (start_prev)
					DoubleLinkList<T>::Join(start_prev, next_head);
				queue.m_head = start;
				queue.m_tail = end;
				queue.m_count = ncount;
				CHECK_LIST(this);
				CHECK_LIST(&queue);
			}
			bool Contain(Pointer ptr)const{
				Pointer head = m_head;
				for (int i = 0; i < m_count && head; i++)
				{
					if (head == ptr)
						return true;
					head = head->GetNext();
				}
				return false;
			}
			Pointer Remove(Pointer ptr)
			{
				DEBUG_ASSERT(Check());
				Pointer cur = m_head;
				if (ptr == m_head)
					ptr = PickHead();
				else if (ptr == m_tail)
					ptr = PickTail();
				else if (ptr != nullptr)
				{
					if (m_count > 0)
					{
						DoubleLinkList<T>::Unlink(ptr);
						m_count--;
					}
					ptr->SetNext(nullptr);
					ptr->SetPrev(nullptr);
				}
				DEBUG_ASSERT(Check());
				return ptr;
				//for (int i = 0; i < m_count; i++)
				//{
				//	if (cur == ptr)
				//	{
				//		DoubleLinkList<T>::Unlink(cur);
				//		m_count--;
				//		return cur;
				//	}
				//	cur = cur->GetNext();
				//}
				//DEBUG_ASSERT(Check());
				//return nullptr;
			}
			void Fix(Pointer prev, Pointer ptr, Pointer next, bool add, int size)
			{
				DEBUG_ASSERT(ptr);
				DEBUG_ASSERT(prev != ptr && ptr != next);
				if (add)
				{
					DEBUG_ASSERT(prev == nullptr && next == nullptr);
					if (m_count == 0){ m_head = m_tail = ptr; }
					while (m_head && m_head->GetPrev()){ m_head = m_head->GetPrev(); }
					while (m_tail && m_tail->GetNext()){ m_tail = m_tail->GetNext(); }
					m_count++;
				}
				else
				{
					DEBUG_ASSERT(ptr->GetNext() == nullptr && ptr->GetPrev() == nullptr);
					if (prev && next){ DEBUG_ASSERT(prev->GetNext() == next && next->GetPrev() == prev); }
					if (ptr == m_head)m_head = next;
					if (ptr == m_tail)m_tail = prev;
					m_count--;
					if (m_count <= 0){ m_tail = m_head = nullptr; }
				}
				DEBUG_ASSERT(size == m_count && m_count>=0);
				DEBUG_ASSERT(Check());
			}
			bool Check()const
			{
				if (m_count == 0){ DEBUG_ASSERT(m_head == nullptr && m_tail == nullptr); }
				else if (m_count == 1)
				{
					DEBUG_ASSERT(m_head == m_tail && m_head->GetPrev() == nullptr && m_head->GetNext() == nullptr);
				}
				else
				{
					DEBUG_ASSERT(m_head && m_tail && m_head != m_tail);
					DEBUG_ASSERT(m_head->GetPrev() == nullptr && m_head->GetNext() != nullptr);
					DEBUG_ASSERT(m_tail->GetNext() == nullptr && m_tail->GetPrev() != nullptr);
				}
				return true;
			}
			bool CheckFull()const
			{
				DEBUG_ASSERT(Check());
				Pointer prev = nullptr;
				Pointer cur = m_head;
				int i = 0;
				for (;cur &&  i < m_count; i++)
				{
					//BASSERT(cur->GetPrev() == prev);
					prev = cur;
					cur = cur->GetNext();
				}
				//BASSERT(m_count == i);
				return true;
			}
		};
	}//namespace base;
}//namespace ss;
